Números Primos

Un buen ejemplo de un programa que requiere de una iteración es determinar si un número es primo. Para determinar si un número es primo, hay que ir pasando por todos sus potenciales divisores y comprobar si lo dividen o no. Por ejemplo, si tenemos el 17, probaremos el 2, el 3, el 4, etc. intentando encontrar un divisor. Si lo encontramos, de hecho, el número no es primo. Si no encontramos, será primo, ya que esa es la definición: es primo aquél número que solo tiene como divisores 1 o él mismo.

Al hacer el programa, solamente hay que tener cuidado de considerar los divisores desde el 2 hasta uno menos que el número en cuestión, que es donde se encuentran los potenciales divisores, y de alguna manera recordar si hemos visto algun divisor o no.

Las 2 primeras instrucciones del programa declaran una variable N y leen el número. Este N es el número que queremos saber si es primo:

int N;
cin >> N;

Seguidamente, declararemos una variable d que contendrá el divisor que estamos considerando y la inicializaremos a 2:

int d = 2;

Aquí es donde comienza el bucle. Hay que recorrer todos los divisores e ir comprobando cada uno. Para recordar si hemos visto alguno que era divisor tendremos la variable primo, que pondremos al valor true al principio:

bool primo = true;

Durante el bucle, si vemos que algun valor de d divide a N pondremos el valor false en la variable primo y al acabar el bucle podremos saber cuál ha sido el resultado.

El bucle es este:

while (d < N) {
   if (N % d == 0) {
      primo = false;
   }
   d++;
}

La expresión N % d == 0 es cierta cuando N es divisible por d (lo cual indica que no es primo). Esa expresión es la que se comprueba para cada d y en caso de ser cierta, la variable primo pasa a ser false.

Al final del bucle, si no hemos entrado en ningun caso en el if, la variable primo aún valdrá true, ya que la hemos inicializado con ese valor.

La estrategia es entonces, suponer que el número es primo e intentar buscar un "contraejemplo", es decir buscar un divisor pasando por todos los posibles a ver si alguno nos hace cambiar de opinión.

El programa entero hasta aquí es:

#include <iostream>
using namespace std;

int main() {
   int N;
   cin >> N;
   int d = 2;
   bool primo = true;
   while (d < N) {
      if (N % d == 0) {
         primo = false;
      }
      d++;
   }
   if (primo) {
      cout << "primo" << endl;
   }
}

while (d < N && primo) {
   if (N % d == 0) {
      primo = false;
   }
   d++;
}